package com.it.od.manual;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author: liminghui
 * @date: 2024/3/28 19:01
 * @version: 1.0
 * @description: 二面笔试题    笔试题：
 * [背包问题]有一个背包，背包容量是M（150）。有K（7）个物品，物品可以是任意重量/价值。
 * 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
 * 测试用例1：
 * M=30, K=3
 * 物品 A B C
 * 重量 28 12 12
 * 价值 30 20 20
 * 答案是: BC
 * 30
 * 3
 * A B C
 * 28 12 12
 * 50 20 20
 * <p>
 * 测试用例2：
 * M=150, K=7
 * 物品 A B C D E F G
 * 重量 35 30 60 50 40 10 25
 * 价值 10 40 30 50 35 40 30
 */
public class BeiBao2 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = Integer.parseInt(sc.nextLine());
        int k = Integer.parseInt(sc.nextLine());
        int[] goods = Arrays.stream(sc.nextLine().split("\\s+")).mapToInt(x -> x.charAt(0) - 'A').toArray();
        int[] weights = Arrays.stream(sc.nextLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
        int[] values = Arrays.stream(sc.nextLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
        int[][] matrix = new int[k][3];

        for (int i = 0; i < goods.length; i++) {
            matrix[i][0] = goods[i];
        }
        for (int i = 0; i < weights.length; i++) {
            matrix[i][1] = weights[i];
        }
        for (int i = 0; i < values.length; i++) {
            matrix[i][2] = values[i];
        }
        int maxValue = dpMaxValue(matrix, k, m);
        System.out.println(maxValue);

    }

    private static int dpMaxValue(int[][] matrix, int k, int m) {
        /**
         * 前i件物品任选，并且总重不超过背包j时 的最大价值
         * 递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+vi)
         */
        int[][] dp = new int[k + 1][m + 1];
        // 第一行都初始化为0
        for (int i = 1; i <= k; i++) { // 物品
            for (int j = 0; j <= m; j++) { // 背包容量
                int wi = matrix[i - 1][1];
                int vi = matrix[i - 1][2];
                if (j >= wi) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wi] + vi);
                } else { //i物品比背包容量大，不选i，最大价值与上次相同
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }
        return dp[k][m];
    }


}
